In computer graphics, smooth colour variation in images is often specified by use of linear or radial colour gradients, which are also known as linear blends and radial blends. More complex colour variation in graphics images is sometimes specified using a gradient mesh, where colours are specified at vertices of the mesh.
Specifying complex and smooth colour variation in graphic images has recently been proposed by firstly specifying colour values along paths (i.e. lines) and secondly determining colour values at positions between paths as a spatial averaging of colour values along nearby paths. In one approach to spatial averaging, colour values between paths are obtained by solving Laplace's equation using finite differences, successive over-relation and/or multigrid, with boundary constraints provided by the colour values along the paths. This approach gives pleasing smooth colour variation.
In recent extensions to this approach, colours are specified immediately to either side of paths, thereby introducing a sharp change in colour, or edge, along the path. Specifying colour variation using paths has the advantage that doing so builds on the natural tendency for artists to draw line-art and for observers to recognise image features from edges. Specifying colour variations using paths is a more compact representation of complex colour variation and more easily editable by graphic artists than the gradient mesh representation.
In computer graphics applications, to render visually appealing images with interactive response times on inexpensive systems, it is important to implement solutions to Laplace's equation with sufficient accuracy while providing fast operation using typical computing resources.
Multigrid provides a popular method of solving Laplace's equation. However, multigrid is a multi-scale and iterative calculation method, which requires repeated access to intermediate, transient image values for a range of image scales. When images are large, this method requires repeated access across a large memory space. Generally, for fast implementation using typical computer processors, non-iterative algorithms with predominantly localised memory access are preferred. Also, using multigrid to solve Laplace's equation is essentially an “all or nothing” method, which requires image values to be computed for the entire image. However, in some applications, only parts of an image are required to be rendered at a time.
Solving Laplace's equation using Multigrid involves setting constraints at grid points, then deriving values at other grid points. When colour values are specified along paths, constraint values at grid points near paths can only be estimated; that is, there is an initial inaccuracy in the constraint rasterisation which is then propagated to derived values. There is a requirement to render videos consisting of successive images specified by colour values along either side of paths, where the path geometry changes from frame to frame. When Multigrid, or other methods of solving Laplace's equation which perform an initial constraint rasterisation, are used to render such videos, the inaccuracies in the constraint rasterisation tend to cause flickering artefacts.